package mashibing.freshman.class06;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 23.合并多个有序链表: https://leetcode.com/problems/merge-k-sorted-lists/
 */
public class Code01_MergeKSortedLists {
	public static class ListNode {
		public int val;
		public ListNode next;
	}

	// 小根堆
	public static class ListNodeComparator implements Comparator<ListNode> {
		@Override
		public int compare(ListNode o1, ListNode o2) {
			return o1.val - o2.val; // o1.val大：正数返回第二个
		}
	}

	public static ListNode mergeKLists(ListNode[] lists) {
		if (lists == null) {
			return null;
		}
		PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());// 优先级队列
		for (int i = 0; i < lists.length; i++) {
			if (lists[i] != null) {
				heap.add(lists[i]);// 抓住每个链表的头
			}
		}
		if (heap.isEmpty()) {
			return null;
		}
		ListNode head = heap.poll();// 弹出一个，作为整体的头部先抓住
		ListNode pre = head;
		if (pre.next != null) {
			heap.add(pre.next);
		}
		while (!heap.isEmpty()) {// 直到小根堆为空
			ListNode cur = heap.poll();//出来一个，头最小，先出来
			pre.next = cur;
			pre = cur;
			if (cur.next != null) {
				heap.add(cur.next);// 进去一个next
			}
		}
		return head;
	}
}
